package linksinglelist;

import java.util.Stack;

/**
 * 无头非循环单链表
 */
public class MySingleList {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public void createList(){
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;
    }
    public void display(){
        ListNode cur = this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public void display(ListNode newHead){
        ListNode cur = newHead;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        node.next=cur;
        this.head=node;
    }
    //尾插法
   public void addLast(int data) {
       ListNode node = new ListNode(data);
       ListNode cur = this.head;
       if(head==null){
           head=node;
       }else {
           while (cur.next!=null){
               cur=cur.next;
           }
           cur.next=node;
       }
   }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)throws MySingleListIndexOutOfException{
        checkIndexAdd(index);
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndexSubOne(index);
        node.next=cur.next;
        cur.next=node;
    }
    private ListNode findIndexSubOne(int index){
        ListNode cur = this.head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;

    }
    private void checkIndexAdd(int index){
        if(index<0|| index>size()){
            throw new MySingleListIndexOutOfException("任意位置插入的时候,index不合法！");
        }
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur=this.head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head==null){
            System.out.println("此时链表为空，不能删除");
            return;
        }
        if(this.head.val==key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                ListNode del = cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
        System.out.println("删除的值不存在");
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head==null)
            return;
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else {
                prev=prev.next;
                cur=cur.next;
            }
        }
        if(this.head.val==key){
            head=head.next;
        }
    }
    //得到单链表的长度
    public int size() {
        int count=0;
        ListNode cur = this.head;
        while (cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 执行clear函数的时候，会将链表中所有节点回收
     */
    public void clear(){
        //this.head=null;比较粗暴
        ListNode cur = this.head;
        ListNode curNext = null;
        while (cur!=null){
            curNext=cur.next;
            cur.next=null;
            cur=curNext;
        }
        head=null;

    }

    /**
     * 反转链表返回新的头节点
     * @return
     */
    public ListNode reverseList(){
        if(head==null)
            return null;
        if(head.next==null)//如果只有一个头节点
            return head;
        ListNode cur = head.next;
        head.next=null;//第一个节点置为空
        while (cur!=null){
            ListNode curNext =cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;

    }

    /**
     * 求链表中间节点
     *
     * @return
     */
    public ListNode middleNode() {
        if(head==null)
            return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){//前后不能反
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    /**
     * 求倒数第K个位置的值
     * @param k
     * @return
     */
    public ListNode FindKthToTail(int k) {
        if(k<=0){
            return null;
        }
        if(head==null)
            return null;
        ListNode fast =head;
        ListNode slow =head;
        while (k-1>0){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    /**
     * 合并两个升序链表
     * @param head1
     * @param head2
     * @return
     */
    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newNode = null;
        ListNode tmp = null;
        ListNode node=null;
        if(head1==null&&head2==null)
            return null;
        if(head1!=null&&head2!=null){
            while(head1!=null&&head2!=null){
                if(head1.val<head2.val){
                    tmp=head1;
                    head1=head1.next;
                }else{
                    tmp = head2;
                    head2=head2.next;
                }
                if(newNode==null){
                    newNode=tmp;
                    node = tmp;
                }else{
                    node.next = tmp;
                    node = node.next;
                }
            }
            if(head1==null){
                node.next=head2;
            }else{
                node.next=head1;
            }
            return newNode;

        }else{
            return head1==null?head2:head1;
        }
    }

    /**
     * 判断是否是回文链表
     * @param head
     * @return
     */
    public boolean chkPalindrome(ListNode head) {
        if(head==null) return false;
        if(head.next==null) return true;//只有一个节点
        //1.找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //2.slow一定是中间节点,翻转
        ListNode cur = slow.next;
        while (cur!=null){
            ListNode curNext = cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //3.slow走到最后一个节点的地方,判断回文
        while (head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            //偶数的情况
            if(head.next==slow){
                return true;
            }

            head=head.next;
            slow=slow.next;
        }
        return true;

    }

    /**
     *
     *现有一链表的头指针 ListNode* pHead，给一定值x，
     * 编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
     * @return
     */
    public ListNode partition(int x) {
        ListNode cur=head;
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        while (cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else {
                    be.next=cur;
                    be=be.next;
                }
            }else {
                if(as==null){
                    as=cur;
                    ae=cur;
                }else {
                    ae.next=cur;
                    ae=ae.next;

                }
            }
            cur=cur.next;

        }
        if(be!=null)
            be.next=as;
        if(as!=null)
            ae.next=null;
        if(bs==null)
            return as;
        return bs;
    }

    /**
     * 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
     * 如果两个链表不存在相交节点，返回 null 。
     * 注：相交的地方是地址相同不是数值相同
     * @param headA
     * @param headB
     * @return
     */
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        int lenA=0;
        int lenB=0;
        ListNode pl=headA;//pl永远指向最长的链表
        ListNode ps=headB;//ps永远指向最短的链表
        while (pl!=null){
            pl=pl.next;
            lenA++;
        }
        while (ps!=null){
            ps=ps.next;
            lenB++;
        }
        pl=headA;
        ps=headB;
        int len=lenA-lenB;
        if(len<0){
            len=lenB-lenA;
            pl=headB;
            ps=headA;
        }
        while (len!=0)
        {
            pl=pl.next;
            len--;
        }
        while (pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;//包括了不相交返回null的情况

    }

    /**
     * 链表是否成环
     * @return
     */
    public boolean hasCycle() {
         if(head==null)
             return false;
         ListNode fast=head;
         ListNode slow=head;
         while (fast!=null&&fast.next!=null){
             fast=fast.next.next;
             slow=slow.next;
             if(fast==slow)
                 return true;
         }
        return false;
    }

    /**
     * 为了测试是否成环函数
     */
    public void createLoop(){
        ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next.next;
    }

    /**
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * @param
     * @return
     */
    public ListNode detectCycle() {
        if(head==null)
            return null;
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        //出循环有两种可能一种是没有环，==null退出的，另一种是break退出的
        if(fast==null||fast.next==null){
            return null;
        }else {
            slow=head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }

    }

    /**
     * 递归逆序打印单链表
     */
    public void display3(ListNode head){
        if(head==null)
            return;
        if(head.next==null){
            System.out.print(head.val+" ");
            return;
        }
        display3(head.next);
        System.out.print(head.val+" ");
       //正序在下面 display3(head.next);
    }

    /**
     * 用栈逆序打印单链表
     */
    public void display4(ListNode head){
        if(head==null)
            return;
        Stack<ListNode> stack = new Stack<>();
        ListNode cur=head;
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (!stack.empty()){
            ListNode p = stack.pop();
            System.out.print(p.val+" ");
        }


    }

}
